import java.util.LinkedList;
import java.util.List;

public class Test {
}
class Solution2 {
    List<List<Integer>> ans = new LinkedList<>();
    private void dfs(int[] candidates, int target,int sum,List<Integer> ret,int j){
        if(sum == target){
            ans.add(new LinkedList<>(ret));
            return;
        }
        for(int i=j; i<candidates.length; i++){
            if(sum + candidates[i] <= target){
                ret.add(candidates[i]);
                dfs(candidates,target,sum+candidates[i],ret,i);
                ret.remove(ret.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> ret = new LinkedList<>();
        dfs(candidates,target,0,ret,0);
        return ans;
    }
}
class Solution {
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    private int dfs(int[][] grid, int i, int j, int n){
        if(grid[i][j] == 2){
            return n==0 ? 1 : 0;
        }
        int t = grid[i][j];
        grid[i][j] = -1;
        int res = 0;
        for(int[] dir : dirs){
            int ni = dir[0]+i; int nj = dir[1]+j;
            if(ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[ni].length && (grid[ni][nj] == 0 || grid[ni][nj] == 2)){
                res += dfs(grid,ni,nj,n-1);
            }
        }
        grid[i][j] = t;
        return res;
    }
    public int uniquePathsIII(int[][] grid) {
        int n = 0;
        int s1 = 0;
        int s2 = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                if(grid[i][j] == 0){
                    n++;
                }else if(grid[i][j]==1){
                    n++;
                    s1 = i;
                    s2 = j;
                }
            }
        }
        return dfs(grid,s1,s2,n);
    }
}